import java.util.Arrays;



public class SwapSort {
    public static void main(String[] args) {
        int [] a = {98,23,1,24,56,33,77,45};
        BubbleSort(a);
//        QuickSort(a);
        QuickSort1(a);
        System.out.println(Arrays.toString(a));
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
    }

    private static void QuickSort1(int[] a) {
        quick1(a,0,a.length -1);
    }

    private static void quick1(int[] a, int start, int end) {
        if(start >= end){
            return;
        }
        int pivot = partition1(a,start,end);
        quick1(a,start,pivot -1);
        quick1(a,pivot+1,end);
        }

    private static int partition1(int[] a, int start, int end) {
        int i = start;
        int pivot = a[start];
        while (start < end){
            while (start < end && a[end] >= pivot){
                end --;
            }
            a[start] = a[end];
            while (start < end && a[start] <= pivot){
                start ++;
            }
            a[end] = a[start];
        }
        a[start] = pivot;
        return start;
    }

    //快速排序
    //时间复杂度:O(nlogn)
    //空间复杂度O(logn)
    //稳定性:不稳定
    private static void QuickSort(int[] a) {
        quick(a,0,a.length-1);
    }

    private static void quick(int[] a, int start, int end) {
        if(start >= end){
            return;
        }
        int pivotHare = partition(a,start,end);
        quick(a,start,pivotHare-1);
        quick(a,pivotHare+1,end);
    }

    private static int partition(int[] a, int left, int right) {
        int i = left ;
        int pivot = a[left];
        while (left < right){
            while (left < right && a[right] >= pivot){
                right -- ;
            }
            while (left < right &&  a[left] <= pivot){
                left ++;
            }
            swap(a,left,right);
        }
        swap(a,left,i);
        return left;
    }


    //时间复杂度O(O^2)
    //空间复杂度O(1)
    //稳定性:稳定
    private static void BubbleSort(int[] a) {
        //控制的最外层的趟数
        boolean flag = true;
        for (int i = 0; i < a.length -1; i++) {
            for (int j = 0; j < a.length -1 -i ; j++) {
                if(a[j] > a[j+1]){
                    swap(a,j,j+1);
                    flag = false;
                }
                if(flag){
                    break;
                }
            }
        }
    }

    private static void swap(int[] a, int j, int i) {
        int tmp = a[j];
        a[j] = a[i];
        a[i] = tmp;
    }
}
